package agorithm.week2.classTwo;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 77. 组合
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 示例:
 *
 * 输入: n = 4, k = 2
 * 输出:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 * @author zcc
 * @date 2021/06/28/18:49
 */
public class Solution {
    private static List<Integer> subStrList = new ArrayList<>();
    private static List<List<Integer>> ans = new ArrayList<>();
    private static Integer n = 0;
    private static Integer k ;
    public static void main(String[] args) {
        System.out.println("combine = " + combine(n, 2));
        System.out.println(1);
    }
    public static List<List<Integer>> combine(int n1, int k1) {
        k = k1;
        n = n1;
        subFunc(1);
        return ans;
    }
    // 枚举1,2,3...n
    public static void subFunc( int index ) {
        //临界条件 sub集合大于k 、 余下的数+sub集合小于k 直接退出
        if (subStrList.size() > k || (subStrList.size() + n - index +1) < k) {
            return;
        }
        // 执行了index=n后的下一轮写结果
        if (index == n + 1) {
            ans.add(new ArrayList<>(subStrList));
        }
        //处理逻辑-》无

        //递归处理
        //1.不选
        subFunc(index + 1);
        //2.选
        subStrList.add(index);
        subFunc(index + 1);
        //还原状态
        subStrList.remove((Integer) index);
    }
}
